The present invention relates to a method for processing an image and more particularly to a method for enabling gray-scale representation by single-bit pixel-depth bitmaps to more closely approach gray-scale representation by traditional photographic methods.
The state-of-the-art of gray-scale representation by single-bit pixel-depth bitmaps is tied to traditional photographic halftone methods. In the halftone printing of continuous tone black and white images, paper or other reflective hardcopy material is imprinted with a large number of circles or dots of black ink with the area of each dot being proportional to the blackness of a corresponding incremental area of the original photograph or image. Each halftone dot appears at a position that is equidistant from each adjacent potential halftone dot position so that each halftone dot occupies a single resolution cell or element within a rectangular array or grid. Traditionally, the printing plates for halftone printing were prepared by photographing the image to be reproduced through a screen having the desired interstitial spacing or cell size. The process, known as screening, results in a photographic negative known as a halftone screen which can be utilized to produce printing plates with the halftone screen exhibiting the desired dot size-image intensity relationship and regularity of spacing between dots.
When an image that has been printed by halftoning is viewed from a distance, the eye performs spatial integration so that various regions of the image are perceived as being black, white, or as being of intermediate intensity, i.e. a shade of gray. The degree to which halftone printing is perceived as being identical to the original black and white image largely depends upon the halftone dot frequency that is employed, which is commonly referred to as the line frequency or screen ruling.
Another important factor is the ability of the printing press or printer to imprint the type of paper or other hardcopy material being employed with halftone dots that correspond in area with the dots of the halftone screen. For example, because of the type of paper employed and the printing presses used, newspaper halftones typically are printed at a line frequency of 60 to 100 lines per inch, while magazine and book halftones typically are printed at a line frequency on the order of 133-150 lines per inch.
Digital halftoning emulates the photographic halftoning process. However, because the digital halftone dot is built up of fixed size picture elements or pixels, centered contiguous placement results in location errors that may reduce the quality of reproduction relative to the precessionary art.
Numerous techniques for improving halftoning processes have been described in the patent literature. U.S. Pat. Nos. 4,633,327 to Roetling; 4,924,301 to Surbrook; 4,942,480 to Shu; 4,945,422 to Ng; 5,196,942 to Shiau; 5,027,078 to Fan; 5,107,346 to Bowers et al; and 5,130,821 to Ng illustrate some of these techniques.
The Roetling patent relates to enhancement halftoning. The method described therein appears to begin with a cell using centered contiguous pixel clusters based on the traditional halftone screen. It uses a system of macro and micro sampling to increase or decrease the black-to-white ratio (contrast) to alter the patterns. This process however fails to address the problem of pixel location errors which occur in conventional digital halftoning processes.
The Surbrook patent relates to an apparatus and method for producing halftone screens from continuous tone intensity signals that are supplied from an optical scanner. A digital signal processor processes the continuous tone intensity values to establish memory maps which, in conjunction with a digital data output device, produce the desired halftone screens. The main problem with the approach employed by Surbrook is a clinging to the traditional photographic halftones centered contiguous pixel clusters. It alters the pattern's dot growth by changing where the next dot falls by analyzing desired screen angles. Because of its dependency on contiguous dot clusters, all meaningful pattern change actually takes place in a very large grid, opening this process to a reduced but still substantial probability of moires and banding.
The Shu patent relates to a technique for reproducing a halftone original with moire reduction and tone adjustment. The technique described therein begins with a traditional photographic halftone and converts it to a digital halftone by assuming a super cell some 7 to 12 times larger and using its macro gray level to determine dot placement alterations. This is coupled with an alternative threshholding method.
The '422 patent to Ng deals with the false density contour of a digital halftone cell--simply the misplacement of the next dot. This placement error is suppressed by means of "weighted probability" using computer-generated random selection. The problem with this approach is that it won't necessarily track with the precessionary art.
The Fan patent relates to a method of unscreening a digitally created halftone image to reconstruct a continuous tone image. This method simply replaces the error-prone digital halftone dot placement with a new dither pattern. The method comprises the steps of determining the parameters of the halftone screen used to generate the halftone image, logically filtering the halftone image to determine approximate continuous tone levels, and optionally, smoothing the continuous tone levels of the reconstructed image to minimize the quantization errors introduced during the original screening or dithering process.
The Bowers patent relates to a process for providing digital halftone images with random error diffusion. This process uses an advanced error diffusion model which assumes that misplacement of dots is derived from the threshold rounding. It includes the diffusion of such thresholding "errors" by spreading them to adjacent pixels and the introduction of computer-generated randomness to hide the problem. This is overcomplicated arbitrary dot placement without reference to the precessionary art.
The '821 patent to Ng relates to a method and apparatus for digital halftoning employing density distribution for selection of a threshold template. The Ng's method recognizes that centered contiguous pixel clusters yield location errors and that placement does not have to be contiguous. But, by altering patterns through referencing adjacent halftone cells instead of the precessionary art, the benefit of increased permutations is countered by potentially equally inaccurate locations, recalling elements of digital posterization at a sacrifice of gray levels.
The Shiau patent relates to a system and method for determining picture element values. The method cuts the cell in half to 2.times.4 and places them at 45 degree angles to each other. While the number of possible gray levels is reduced to 8 plus white, the method purports to use but 5. The dot growth pattern is an arbitrary one and has to rely on error diffusion for even a semblance of proper placement.
One method which has been proposed for producing halftone images is the dither method. U.S. Pat. Nos. 4,651,293 to Kato; 4,736,254 to Kotera et al.; 4,800,443 to Crinon et al.; 4,866,534 to Tada; and 5,053,887 to Thompson illustrate methods for producing images which can be termed "dither" methods.
The Kato patent relates to an image processing system which processes an input image such as a halftone image having a high periodicity (adjacent patterns are the same) into a two-level image by use of dither matrices. Peaks of an auto-correlation of the image are calculated and, then, a mean period of the calculated peaks. An adequate dither matrix is selected in response to the calculated mean period. The problem with computational generation of patterns is that there are so many (more than 20 trillion for a 4.times.4 cell).
The Kotera et al. patent relates to a method and apparatus for generating pseudo-halftone dots by comparing gray scale values of an original with dither threshold values stored in cells of a matrix array divided into imaginary matrices of elemental areas each containing one cell. This patent takes the position that if one dither pattern doesn't achieve the desired results, combining elements of three would be better. It chooses between the three pattern generators (Bayer, mesh and spiral) for each cell. This yields a large number of permutations and is quite computational.
The Crinon patent relates to a method and apparatus for carrying out a dithering operation. While this method uses the precessionary art to determine pixel location, its preferred grid is 16.times.16 which would yield an enormous number of pattern permutations. As a result, a great computational effort has to be undertaken.
The Tada patent relates to an image processing apparatus for transforming eclectic data of a halftone image into a bi-level image by using a dither matrix. The apparatus has a plurality of dither matrices of different patterns to each other. The dither matrices are chosen to remove textures due to dither processing. The method employed by Tada begins with a bit-mapped halftone image which is believed to mean cell-centered contiguous pixel clusters. This pattern is replaced by new dither patterns generated from the halftone pattern and not the precessionary art. The method seeks to avoid any checkered gray pattern.
The Thompson patent relates to a technique for producing a fine grained dithered halftone image having an increased number of gray levels. This technique increases a 4.times.4 cell by one additional pixel (placed just above the upper lefthand pixel). This new polygon cell is interleaved with similar adjoining cells to avoid duplicating adjacent patterns to reduce moires and banding. This is coupled with an alternative thresholding model. All in all, this technique is very computationally-intensive.
Still other techniques for processing images are shown in U.S. Pat. Nos. 4,741,046 to Matsunawa et al.; 4,752,822 to Kawamura; 4,926,248 to Kobayashi et al.; 5,083,210 to Reilly et al.; and 5,200,831 to Tai. The Matsunawa et al. patent relates to a method of discriminating pictures. The method described therein starts with a bitmap and attempts to ameliorate the gray level versus detail trade-off by computational discrimination between inherent patterns halftone, line and continuous-tone. The method appears to select a new pattern depending on this discrimination. It seems highly unlikely that enough information could be extracted from error-prone bitmap to correct it without going back to the precessionary art.
The Kawamura patent relates to a color halftone image processing apparatus. It appears that Kawamura believes that pattern errors are somehow related to the square pixel grid. A new grid of 20 pixels shaped like a plus sign is created so that it will interleave with other similar cells. A new pattern is generated for this polygon assuming that adjacent patterns, because they are not perpendicular, will eliminate macro cell patterns. The pattern generation is arbitrary and unwanted pattern juxtapositions are still probable.
The Kobayashi et al. patent relates to a scanning recording type printing method and apparatus for increasing image quality by controlling the dot locations within image pixels. The method begins with continuous tone precessionary art and creates a pattern that adds one extra contiguous black dot in the scan line for each black dot placed and one extra contiguous white dot in the scan line for each white dot placed. If accurately derived from the precessionary art, this approach could generate a pattern suitably diverse to avoid moires and banding, but at a cost of doubling the matrix size and the resultant location errors.
The Reilly et al. patent relates to a technique for eliminating the contouring on displayed gray level images. The method described therein acknowledges digital halftoning dither pixel misplacements, but instead of correctly placing then using the precessionary art, it uses "pseudo random noise" in the form of additional black pixels to "hide" such location errors.
The Tai patent relates to a method and arrangement for locally switching gray dot types to reproduce an image with gray level printing. The method described in this patent recognizes that a unified model is needed to render both detail and gray for different renderings type or line drawings and grayscale. It also recognizes that contiguous clusters (threshold dots) are better for the former and non-contiguous patterns (mixed dots) are better for the latter. The process primarily distinguishes between the two and chooses one pattern or the other. The patterns are arbitrary since 3 bits or 4 bits are used to described them.